interface TreeHelperConfig {
  id: string
  children: string
  pid: string
}
const DEFAULT_CONFIG: TreeHelperConfig = {
  id: 'id',
  children: 'children',
  pid: 'pid',
}

function getConfig(config: Partial<TreeHelperConfig>) {
  return Object.assign({}, DEFAULT_CONFIG, config)
}

/**
 * 集合转成tree
DEFAULT_CONFIG: TreeHelperConfig = {
  id: 'id',
  children: 'children',
  pid: 'pid'
}
 * @param list
 * @param config
 */
export function listToTree<T = any>(list: any[], config: Partial<TreeHelperConfig> = {}): T[] {
  const conf = getConfig(config) as TreeHelperConfig
  const nodeMap = new Map()
  const result: T[] = []
  const { id, children, pid } = conf

  for (const node of list) {
    node[children] = node[children] || []
    nodeMap.set(node[id], node)
  }
  for (const node of list) {
    const parent = nodeMap.get(node[pid])
    ;(parent ? parent.children : result).push(node)
  }
  return result
}

/**
 * tree转成集合
DEFAULT_CONFIG: TreeHelperConfig = {
  children: 'children',
}
 * @param tree
 * @param config
 */
export function treeToList<T = any>(tree: any, config: Partial<TreeHelperConfig> = {}): T[] {
  config = getConfig(config)
  const { children } = config
  const result: T[] = []

  const traverse = (nodes: any[]) => {
    for (const node of nodes) {
      result.push(node)
      if (node[children!])
        traverse(node[children!])
    }
  }
  traverse(tree)
  return result
}

/**
 * 根据条件找到一个节点
DEFAULT_CONFIG: TreeHelperConfig = {
  children: 'children',
}
 * @param tree
 * @param func
 * @param config
 */
export function findNode<T = any>(tree: any, func: Fn, config: Partial<TreeHelperConfig> = {}): T | undefined {
  config = getConfig(config)
  const { children } = config
  const list = [...tree]
  for (const node of list) {
    if (func(node))
      return node
    node[children!] && list.push(...node[children!])
  }
}

/**
 * 找到符合条件多个节点的，返回list
DEFAULT_CONFIG: TreeHelperConfig = {
  children: 'children',
}
 * @param tree
 * @param func
 * @param config
 */
export function findNodeAll<T = any>(tree: any, func: Fn, config: Partial<TreeHelperConfig> = {}): T[] {
  config = getConfig(config)
  const { children } = config
  const list = [...tree]
  const result: T[] = []
  for (const node of list) {
    func(node) && result.push(node)
    node[children!] && list.push(...node[children!])
  }
  return result
}

/**
 * 找到符合条件的最终节点，并将节点的父级一级一级向上全部返回，返回list ：【...祖，父，子】
DEFAULT_CONFIG: TreeHelperConfig = {
  children: 'children',
}
 * @param tree
 * @param func
 * @param config
 */
export function findPath<T = any>(tree: any, func: Fn, config: Partial<TreeHelperConfig> = {}): T[] | null {
  config = getConfig(config)
  const path: T[] = []
  const list = [...tree]
  const visitedSet = new Set()
  const { children } = config
  while (list.length) {
    const node = list[0]
    if (visitedSet.has(node)) {
      path.pop()
      list.shift()
    }
    else {
      visitedSet.add(node)
      node[children!] && list.unshift(...node[children!])
      path.push(node)
      if (func(node))
        return path
    }
  }
  return null
}

/**
 * 找到符合条件的最终节点集合，并将节点的父级一级一级向上全部返回，返回list ：【【...祖，父，子】，【...祖，父，子】】
DEFAULT_CONFIG: TreeHelperConfig = {
  children: 'children',
}
 * @param tree
 * @param func
 * @param config
 */
export function findPathAll(tree: any, func: Fn, config: Partial<TreeHelperConfig> = {}) {
  config = getConfig(config)
  const path: any[] = []
  const list = [...tree]
  const result: any[] = []
  const visitedSet = new Set()
  const { children } = config
  while (list.length) {
    const node = list[0]
    if (visitedSet.has(node)) {
      path.pop()
      list.shift()
    }
    else {
      visitedSet.add(node)
      node[children!] && list.unshift(...node[children!])
      path.push(node)
      func(node) && result.push([...path])
    }
  }
  return result
}

/**
 * 根据条件过滤tree
DEFAULT_CONFIG: TreeHelperConfig = {
  children: 'children',
}
 * @param tree
 * @param func
 * @param config
 */
export function filterTree<T = any>(tree: T[], func: (n: T) => boolean, config: Partial<TreeHelperConfig> = {}): T[] {
  config = getConfig(config)
  const children = config.children as string
  function listFilter(list: T[]) {
    return list
      .map((node: any) => ({ ...node }))
      .filter((node) => {
        node[children] = node[children] && listFilter(node[children])
        return func(node) || (node[children] && node[children].length)
      }) as T[]
  }
  return listFilter(tree)
}

/**
 * 遍历tree
DEFAULT_CONFIG: TreeHelperConfig = {
  children: 'children',
}
 * @param tree
 * @param func
 * @param config
 */
export function forEachTree<T = any>(tree: T[], func: (n: T) => any, config: Partial<TreeHelperConfig> = {}): void {
  config = getConfig(config)
  const list: any[] = [...tree]
  const { children } = config
  for (let i = 0; i < list.length; i++) {
    // func 返回true就终止遍历，避免大量节点场景下无意义循环，引起浏览器卡顿
    if (func(list[i]))
      return

    children && list[i][children] && list.splice(i + 1, 0, ...list[i][children])
  }
}

/**
 * 对树结构中每个数据进行指定函数的变换，并返回新的树
 */
export function treeMap<T extends Record<string, any>, U = T>(treeData: T[], opt: { children?: string, conversion: Fn<T, U> }): U[] {
  // @ts-ignore
  return treeData.map(item => treeMapEach(item, opt)) as U[]
}

// ************************************************内部方法**************************************************************************
/**
 * @description: 对树结构中单个数据进行指定函数的变换，并返回新的树
 */
function treeMapEach<T extends Record<string, any>, U = T>(
  data: T,
  {
    children = 'children',
    conversion,
  }: { children?: string, conversion: Fn<T, U> },
) {
  const haveChildren
    = Array.isArray(data[children]) && data[children].length > 0
  const conversionData = conversion(data) || {}
  if (haveChildren) {
    return {
      ...conversionData,
      [children]: data[children].map((i: T) =>
        treeMapEach(i, {
          children,
          conversion,
        }),
      ),
    }
  }
  else {
    return {
      ...conversionData,
    }
  }
}
